# 93.复原IP地址
# 有效IP地址正好由四个整数（每个整数位于0到255之间组成，且不能含有前导0），整数之间用'.'分隔。
# 例如："0.1.2.201"和"192.168.1.1"是有效IP地址，但是"0.011.255.245"、"192.168.1.312"和"192.168@1.1"是无效IP地址。
# 给定一个只包含数字的字符串s ，用以表示一个IP地址，返回所有可能的有效IP地址，这些地址可以通过在s中插入'.'来形成。你不能重新排序或删除
# s中的任何数字。你可以按任何顺序返回答案。
#
# 示例1：
# 输入：s = "25525511135"
# 输出：["255.255.11.135", "255.255.111.35"]
#
# 示例2：
# 输入：s = "0000"
# 输出：["0.0.0.0"]
#
# 示例3：
# 输入：s = "101023"
# 输出：["1.0.10.23", "1.0.102.3", "10.1.0.23", "10.10.2.3", "101.0.2.3"]
#

class Solution:
    #参考回文串切割，修修补补做出来了
    def isvalid(self,s):
        size = len(s)
        if size > 3: # 分割长度大于3不合法
            return False
        if int(s) > 255: # 数值大于255不合法
            return False
        if size != len(str(int(s))): # 0开头的不合法
            return False
        return True

    def restoreIpAddresses(self, s: str):
        res = []
        path = []
        for i in s:
            if not i.isdigit():
                return res
        def backtracking(s,index):
            if len(path) > 4: # 自己感觉的剪枝
                return
            if index >= len(s) and len(path) == 4:
                tmp = ".".join(path[:])
                res.append(tmp)
                return
            for i in range(index,len(s)):
                if self.isvalid(s[index:i+1]):
                    path.append(s[index:i+1])
                    backtracking(s,i+1)
                    path.pop()
                else:
                    continue
        backtracking(s,0)
        return res

if __name__ == '__main__':
    s = "25525511135"
    tmp = Solution()
    res = tmp.restoreIpAddresses(s)
    print(res)

